home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 247_01 / brute.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-17  |  1.1 KB  |  49 lines
  1. /*
  2.  *   Program to factor numbers using brute force.
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include "miracl.h"
  7. #define LIMIT 15000
  8.  
  9. main()
  10. { /* find factors by brute force division */
  11.     big x,y;
  12.     int n,p;
  13.     int *primes;
  14.     mirsys(50,MAXBASE);
  15.     x=mirvar(0);
  16.     y=mirvar(0);
  17.     primes=gprime(LIMIT);
  18.     n=0;
  19.     p=primes[0];
  20.     printf("input number to be factored\n");
  21.     cinnum(x,stdin);
  22.     if (prime(x))
  23.     {
  24.         printf("this number is prime!\n");
  25.         exit(0);
  26.     }
  27.     printf("factors are \n");
  28.     while (size(x)>=p)
  29.     { /* try division by each prime in turn */
  30.         if (p==0)
  31.         { /* run out of primes */
  32.             printf("composite factor ");
  33.             cotnum(x,stdout);
  34.             exit(0);
  35.         }
  36.         if (subdiv(x,p,y)==0)
  37.         { /* factor found */
  38.             copy(y,x);
  39.             printf("prime factor     ");
  40.             printf("%d\n",p);
  41.             if (prime(x)) break;
  42.         }
  43.         else p=primes[++n];
  44.     }
  45.     printf("prime factor     ");
  46.     cotnum(x,stdout);
  47. }
  48.  
  49.